// 加入差值绝对值直到长度固定
// 给定一个非负数组arr，计算任何两个数差值的绝对值
// 如果arr中没有，都要加入到arr里，但是只加一份
// 然后新的arr继续计算任何两个数差值的绝对值，
// 如果arr中没有，都要加入到arr里，但是只加一份
// 一直到arr大小固定，返回arr最终的长度
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

// 数组的长度不再发生变化，即可判断完成
bool finish(vector<int>& nums, unordered_set<int>& set)
{
    int len = nums.size();
    // 枚举任意两个数的绝对值，如果该绝对值不存在
    // 就插入到 nums 中
    for(int i = 0; i < len; ++i)
    {
        for(int j = i + 1; j < len; ++j)
        {
            int num = abs(nums[j] - nums[i]);
            if(!set.count(num))
            {
                nums.push_back(num);
                set.insert(num);
            }
        }
    }
    return len == nums.size();
}

// 暴力方法
// 为了验证
int len1(vector<int>& arr)
{
    vector<int> nums;
    unordered_set<int> set;
    for(int x : arr)
    {
        nums.push_back(x);
        set.insert(x);
    }
    while(!finish(nums, set));
    return nums.size();
}

// 求最大公约数
int gcd(int m, int n)
{
    return n == 0 ? m : gcd(n, m % n);
}

// 正式方法
// 时间复杂度O(n)
int len2(vector<int>& arr)
{
    int mx = 0;
    // 找到任意一个非0的值
    int g = 0;
    for(int x : arr)
    {
        mx = max(mx, x); // 求最大值
        if(x != 0) g = x;
    }
    // 数组中都是0
    if(g == 0) return arr.size();
    // 不都是0
    // 0 7次
    // 5 5次
    unordered_map<int, int> cnts;
    for(int x : arr)
    {
        if(x != 0) g = gcd(g, x);
        ++cnts[x]; // 求每个数字的出现次数
    }
    int ans = mx / g;
    int maxCnt = 0;
    for(auto& [key, _] : cnts)
    {
        if(key != 0) ans += cnts[key] - 1;
        maxCnt = max(maxCnt, cnts[key]); // 求最多的出现次数
    }
    ans += cnts.count(0) ? cnts[0] : (maxCnt > 1 ? 1 : 0);
    return ans;
}

vector<int> randomArray(int n, int v)
{
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) arr[i] = rand() % v;
    return arr;
}

int main()
{
    int N = 50;
    int V = 100;
    int testTimes = 20000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 1;
        vector<int> nums = randomArray(n, V);
        int ans1 = len1(nums);
        int ans2 = len2(nums);
        if(ans1 != ans2) cout << "出错了！" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}